package com.bee.剑指offer;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。
 * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 *
 * @Author yong.Mr
 * @data 2021-04-23
 * @version 1.0.0
 */
public class 复杂链表的复制 {

    /**
     * 链表复制直接使用Map<RandomListNode,RandomListNode>来存储老节点和新节点的关系
     */
    public RandomListNode Clone(RandomListNode pHead) {
        Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
        RandomListNode temp = pHead;
        while (temp != null) {
            RandomListNode newNode = new RandomListNode(temp.label);
            map.put(temp,newNode);
            temp = temp.next;
        }
        temp = pHead;
        while (temp != null) {
            RandomListNode randomListNode = map.get(temp);
            randomListNode.next = temp.next == null ? null : map.get(temp.next);
            randomListNode.random = temp.random == null ? null : map.get(temp.random);
            temp = temp.next;
        }
        return map.get(pHead);
    }


    public static RandomListNode clo(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while (cur != null) {
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while (cur != null) {
            RandomListNode randomListNode = map.get(cur);
            randomListNode.next = cur.next == null ? null : map.get(cur.next);
            randomListNode.random = cur.random == null ? null : map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }

    public static void main(String[] args) {

    }
}
